// 给你一个仅由大写英文字母组成的字符串，
// 你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。
// 在执行上述操作后，找到包含重复字母的最长子串的长度。

const characterReplacement = function (s: string, k: number): number {
    let left = 0;
    let right = 0;
    let res = 0;
    let maxFreq = 0; // 非常巧妙地地方，维护最大频数
    const letterMap = new Map<string, number>(); // 哈希表记录字母频数
    while (right < s.length) {
        let rightCount = letterMap.get(s[right]) || 0;
        // 更新字符计数
        letterMap.set(s[right], rightCount + 1);
        // 右移后需要维护最大字符频数，最大频数可能受右移新读入字符而发生改变
        maxFreq = Math.max(maxFreq, rightCount + 1);
        right++;// 右指针右移
        // 如果k值不够了
        if (right - left > maxFreq + k) {
            let leftCount = letterMap.get(s[left]) || 1;
            letterMap.set(s[left], leftCount - 1);
            left++;// 左指针右移
        }
        // 动态维护结果
        res = Math.max(res, right - left);
    }
    return res;
};


// 这道题目是一道难度较大的滑动窗口相关的题目
// 首先看到连续最长子串这种要求，可以下意识地相当双指针与滑动窗口解法
// 但落实到具体的操作并不好想,这里首先需要想到维护子串内频数最大的字母
// 要实现这个并不简单，因为在滑动的过程中，总是会有元素建少或者元素增加，
// 而且加入或者移除的元素是完全独立的，不好分析
// 这里想到巧妙的办法是维护一个频数哈希表，我们每次需要读取当前的右指针对应字母的频数
// 而频数哈希表对应的是当前子串中各个字母的计数
// 然后在每一轮移动中不断地维护最大频数，因为每一次右边界读入一个字符，字符频数增加，才会使得 maxCount 增加
// 而我们判断k是否够用的方法则是通过数学判断：right - left > maxFreq + k ？
// 在这里如果引入currK等计数变量会白白增加复杂性，如果发现k不够用就需要更新哈希表然后左指针右移
// 在每一轮的循环结束后都需要维护最长结果。
// 本题的关键在于需要想到通过子串频数哈希表去维护子串中的最大字符频数。